package org.xteam.engine;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.xteam.engine.geom.Point2D;
import org.xteam.engine.object.Polygon;

public class Rasterizer {
	
	private static class Edge implements Comparable<Edge> {

		private int x;
		private int dx;
		private int dy;
		private int xinc;
		private int cumul;
		private int count;
		
		public Edge(Point2D p1, Point2D p2) {
			this.x = p1.x;
			this.dx = p2.x - p1.x;
			this.dy = p2.y - p1.y;
			this.xinc = (dx > 0) ? 1 : -1;
			dx = Math.abs(dx);
			dy = Math.abs(dy);
			if (dx > dy) {
				cumul = dx;
			} else {
				cumul = dy;
			}
			count = dy;
		}

		public boolean isAtEnd() {
			return count == 0;
		}

		public void update() {
			--count;
			if (dx > dy) {
				for (int i = 0; i < dx; ++i) {
					x += xinc;
					cumul += 2 * dy;
					if (cumul >= 2 * dx) {
						cumul -= 2 * dx;
						break;
					}
				}
			} else {
				cumul += 2 * dx;
				if (cumul >= 2 * dy) {
					cumul -= 2 * dy;
					x += xinc;
				}
			}
		}

		@Override
		public int compareTo(Edge o) {
			return x - o.x;
		}
	}
	
	private static class EdgeList {
		
		private int y;
		private List<Edge> edges = new ArrayList<Edge>();
		
		public EdgeList(int y) {
			this.y = y;
		}

		public void addEdge(Point2D p1, Point2D p2) {
			int i = 0;
			while (i < edges.size()) {
				Edge edge = edges.get(i);
				if (edge.x < p1.x) {
					break;
				}
				++i;
			}
			edges.add(i, new Edge(p1, p2));
		}
	}
	
	private List<EdgeList> edgeLists = new ArrayList<EdgeList>();
	private PixelBuffer pixelBuffer;

	public Rasterizer(PixelBuffer pixelBuffer) {
		this.pixelBuffer = pixelBuffer;
	}

	public void drawPolygon(Polygon polygon) {
		insertPolygon(polygon);
		drawDisplayList();
	}
	
	private void drawDisplayList() {
		int y = 0;
		List<Edge> activeEdges = new ArrayList<Edge>();
		int currentEdgeListIndex = 0;
		while (y < pixelBuffer.getHeight()) {
			
			// remove finished edges
			Iterator<Edge> it = activeEdges.iterator();
			while (it.hasNext()) {
				Edge e = it.next();
				if (e.isAtEnd()) {
					it.remove();
				}
			}
			
			// insert new edges
			if (currentEdgeListIndex < edgeLists.size()
					&& edgeLists.get(currentEdgeListIndex).y == y) {
				for (Edge edge : edgeLists.get(currentEdgeListIndex).edges) {
					int i = 0;
					while (i < activeEdges.size()) {
						if (activeEdges.get(i).x > edge.x) {
							break;
						}
						++i;
					}
					activeEdges.add(i, edge);
				}
				++currentEdgeListIndex;
			}
			
			// draw spans
			for (int i = 0; i < activeEdges.size(); i += 2) {
				Edge left  = activeEdges.get(i);
				Edge right = activeEdges.get(i+1);
				for (int x = left.x; x < right.x; ++x) {
					pixelBuffer.putPixel(x, y);
				}
			}
			
			// update edges
			for (Edge e : activeEdges) {
				e.update();
			}
			
			// reorder edges
			Collections.sort(activeEdges); // est ce utilise si les polygones sont convexes ?
			
			++y;
		}
	}

	private void insertPolygon(Polygon polygon) {
		Point2D first = null;
		Point2D previous = null;
		for (Point2D point : polygon.getPoints()) {
			if (first == null) {
				first = point;
			}
			if (previous != null) {
				addEdge(previous, point);
			}
			previous = point;
		}
		if (previous != null && first != null) {
			addEdge(previous, first);
		}
	}

	private void addEdge(Point2D p1, Point2D p2) {
		if (p1.y != p2.y) {
			if (p1.y > p2.y) {
				Point2D tmp = p1;
				p1 = p2;
				p2 = tmp;
			}
			EdgeList edgeList = null;
			for (int i = 0; i < edgeLists.size(); ++i) {
				EdgeList el = edgeLists.get(i);
				if (el.y == p1.y) {
					edgeList = el;
					break;
				} else if (el.y > p1.y) {
					edgeList = new EdgeList(p1.y);
					edgeLists.add(i, edgeList);
					break;
				}
			}
			if (edgeList == null) {
				edgeList = new EdgeList(p1.y);
				edgeLists.add(edgeList);
			}
			edgeList.addEdge(p1, p2);
		}
	}
}
